package 力扣.栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/*
【题目】给定一个正整数数组和 k，要求依次取出 k 个数，输出其中数组的一个子序列，需要满足：1. 长度为 k；2.字典序最小。

        输入：nums = [3,5,2,6], k = 2
        输出：[2,6]

解释：在所有可能的解：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 字典序最小。
所谓字典序就是，给定两个数组：x = [x1,x2,x3,x4]，y = [y1,y2,y3,y4]，比较同一个索引的元素，找到较小的，则说明它的字典序较小，若当前索引的两个元素相等，则比较下一个索引
*/
public class 字典序最小的k个数的子序列 {
    public static void main(String[] args) {
        int[] ints  = {3,5,2,6,1,0};
        int k = 2;
        int[] smallSeq = findSmallSeq2(new int[]{9,2,4,5,1,2,6,3,100,4}, 1);
        System.out.println(Arrays.toString(smallSeq));
    }

    /**
      保证（栈中元素+剩余元素）大于 k 个时，使用单调递增栈弹栈
     */
    public static  int[] findSmallSeq(int[] A,int k){
        if (A.length == k){
            return A;
        }
        LinkedList<Integer> reS = new LinkedList<>();
        int[] re = new int[k];
        for (int i = 0; i < A.length; i++) {
            int te = A[i];
            while (!reS.isEmpty() && reS.peek() > te && (reS.size()+ A.length - i) > k ){//保证（栈中元素+剩余元素）大于 k 个时，才能进行弹栈
                    reS.pop();
            }
            if (reS.size() < k){//必入栈
                    reS.push(te);
                }
            }
        while (!reS.isEmpty()){
            re[k - 1] = reS.pop() ;
            k--;
        }
       return re;
    }
    public static  int[] findSmallSeq2(int[] A,int k){
        if (A.length == k){
            return A;
        }
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < A.length; i++) {
            while (!stack.isEmpty() && stack.peek() > A[i] && (stack.size() + (A.length - i)) > k){
                stack.pop();
            }
            stack.push(A[i]);
        }
        int[] re = new int[k];
        // 如果递增栈里面的数太多，那么我们只需要取出前k个就可以了。
        // 多余的栈中的元素需要扔掉。
        while (stack.size() > k) {
            stack.pop();
        }
        while (!stack.isEmpty()){
            re[k - 1] = stack.pop();
            k--;
        }
        return re;


    }
}
